1. Field of Invention
This invention relates generally to computer software systems and more specifically to computer software systems that processes computer programs prior to execution.
2. Discussion of Related Art
Computer programs are often written as a series of instructions. Some instructions may specify operations that are performed when the program is executed. Other instructions may control program flow by specifying the order or conditions under which other instructions are executed. Yet other instructions may specify parameters of execution of the program, such as how information representing variables in the program is stored in memory attached to a processor executing the program.
In high level programming languages, the instructions do not necessarily correspond in a one-to-one relationship to instructions that can be executed by the platform on which the software will be executed. Rather, the instructions may be in a form that a human can understand. The program in this form must first be processed into a form appropriate to be executed by a specific platform. Platforms with different processors or different operating systems may require the program be represented differently for proper execution.
Software tools are usually used to convert the program into a form that may be executed by a specific platform. An example of a tool is a compiler. In addition to simply expressing each high level instruction as a series of instructions that a processor can execute, these tools may optimize the program or otherwise process it. Examples of processing that may be performed on a program as it is being prepared for execution are dead code removal, scheduling, code motion and common sub-expression elimination.
In processing the program, the software tool often coverts the code to an intermediate representation. The intermediate representation provides a convenient representation of the operations that must be performed when the program is executed. It also provides information about the variables that will be used to store information while the program executes, including information about the portions of the program which those variables are used. The intermediate representation also provides information about the program flow-between operations.
Often, the intermediate representation describes the flow of the program as a “flow graph.” A flow graph contains blocks and edges. Each block represents a collection of instructions that will be executed in a prescribed order so that there is one starting point and one ending point for the block. In the flow graph, edges interconnect the blocks to indicate the order in which the blocks are executed. The flow graph includes edges that represent every possible path through the blocks that could be taken when the program is executed. Multiple paths may connect to each block.
Information about program flow and memory requirements can be used to process the program in multiple ways. It may be used to prepare instructions implementing the program for execution on a specific platform or may be used to make optimizations in a platform independent way.
FIG. 1A shows a program 100 written in the C# high level programming language. Program 100 includes a series of instructions, such as instructions 112 and 114. In the example of FIG. 1A, instructions 112 and 114 are “definitions” of the variable Y. As used herein, the term “definition” refers generally to any instruction that may create, modify or otherwise alter the information associated with a variable.
Program 100 also includes an instruction 120 that defines the beginning of a try body. Bracket 121 defines the end of the try body that begins with instruction 120. A try body is also sometimes called a “protected region of code.”
The try body may work in connection with one or more protecting regions of code, which are sometimes also referred to as “protector regions” or “handlers.” Here, two handlers are illustrated, an exception handler and a “finally” handler. An exception handler is also sometimes called a “catch handler.” The exception handler begins with the instruction 122 and ends with bracket 123. The program 100 also has a finally handler associated with the try body. The finally handler begins with the instruction 124 and ends at the bracket 125.
Program 100 also includes instructions, such as instruction 130, located outside of the try body.
The operation of the handlers is illustrated by FIG. 1B, which illustrates execution of program 100. In this example, the try body 140 includes the first executable instructions within program 100. In normal operation, try body 140 will be executed first and the instructions in the try body 140 will be executed in an order specified by those instructions.
The instructions in the finally handler 144 are executed as the final instructions in the try region made up of try body 140, exception handler 142 and finally handler 144. In normal execution, when execution of the instructions within the try body 140 is done, execution passes to the finally handler 144.
After the instructions in finally handler 144 are executed, instructions in program 100 following try region 140 are executed. Here those instructions are in region 150.
The instructions in exception handler 142 are executed only if an exception occurs while instructions within try body 140 are being executed. An exception condition may be created by the execution of special exception instructions in program 100. However, in most cases exception conditions are caused by execution of an instruction within program 100 commanding the platform executing program 100 to perform an operation that is considered an illegal operation for that platform. Examples of illegal operations are divide by zero and instructions that instruct the platform to access memory at an address that is not installed in the system or is reserved by the operating system.
Exception handler 142 may be considered to be executed asynchronously. As used herein, the term “asynchronous” describes an event, such as an exception, that occurs in response to a condition during program execution other than an instruction in the program intended to cause the resulting transfer of control. Finally handler 144 may also be considered to be executed asynchronously because it could be executed following exception handler 142.
FIG. 1C is a flow graph that shows in more detail the possible paths from try body 140 to exception handler 142, thereby illustrating a problem that can arise from asynchronous events. Each of the instructions in try region 140 is represented as a block such as 162, 164, 166, 168, 170 or 172. Edges, such as edge 178 show the normal flow between the blocks. Edges 180A, 180B, 182, 184, 186, 188, 190 and 192 represent asynchronous edges. The asynchronous edges represent the possibility that execution of any instruction in try body 140 could cause program flow to be diverted to exception handler 142. Edge 180A represents the possibility that an error may occur prior to the execution of any instruction in try body 140. Edge 180B represents the transfer of control that occurs at the end of execution of exception handler 142.
Some prior art software tools have formed intermediate representations of programs including try regions from which asynchronous transfer of control is possible by adding an edge from every possible instruction from which flow could be transferred to a handler region 142 as illustrated in FIG. 1C. Adding edges from every instruction in the try region has been used to avoid errors that could result from processing an incomplete representation of a program.
However, a drawback of adding asynchronous edges using the “all possible edges” approach illustrated in FIG. 1C is the resulting complexity of the flow graph. Program 100 represents a relatively simple program. A commercially significant program may contain many more instructions than illustrated. In addition, a program may contain multiple try regions with multiple handlers associated with each region. Further, try regions may be embedded within other try regions. As a further complexity, it is not necessary that flow return to the end of a try body after execution of a handler. A handler may divert program flow to any location within the program or to any one of multiple locations in the program with the specific location determined by conditions at runtime. As a result, adding all possible asynchronous edges to a flow graph greatly complicates the flow graph. Processing a program based on such a flow graph may therefore take considerable time or computer resources.
In some prior art software tools, the complexity resulting from adding all possible asynchronous edges is avoided by creating flow graphs without asynchronous edges. However, to compensate, tools processing programs based on these flow graphs do not perform operations on instructions in the try regions that rely on an accurate representation of all possible flow paths. While processing a program in this fashion may be faster or simpler, the benefits of the software tools are not achieved.
It would be desirable to have a method of representing programs including asynchronous transfer of control to facilitate processing of the programs by software tools.